public class demo1 {
    class Solution {
        int ret=0;
        int n;
        public int lengthOfLIS(int[] nums) {
            n=nums.length;
            //动态规划
            // int n=nums.length;
            // int[]dp=new int[n+1];
            // for(int i=n-2;i>=0;i--){
            //     for(int j=i+1;j<n;j++){
            //         if(nums[j]>nums[i]){
            //             dp[i]=Math.max(dp[i],dp[j]+1);
            //         }
            //     }
            //     ret=Math.max(ret,dp[i]);
            // }
            // return ret+1;//只有一数时也是长度为一

            //记忆搜索
            int []memo=new int[n];
            int max=0;
            for(int i=0;i<n;i++){
                max=Math.max(max,dfs(nums,i,memo));
            }

            return max;
        }
        public int dfs(int[]nums,int pos,int[]memo){
            if(memo[pos]!=0){
                return memo[pos];
            }
            int temp=1;
            for(int x=pos+1;x<n;x++){
                if(nums[x]>nums[pos]){
                    temp= Math.max(temp,dfs(nums,x,memo)+1);
                    memo[pos]=temp;
                }
            }
            return temp;
        }
    }
}
